# 动态规划类
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 法一：空间复杂度为0(1)
        # if n == 1:
        #     return 1
        # elif n == 2:
        #     return 2
        # else:
        #     a, b = 1, 2
        #     for i in range(3, n+1):
        #         c = a + b
        #         a = b
        #         b = c
        #     return c
        # 法二：空间复杂度为O(n)
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            dp = [0] * (n+1)
            dp[1] = 1
            dp[2] = 2
            for i in range(3, n+1):
                dp[i] = dp[i-1] + dp[i-2]
            return dp[n]
        
if __name__ == '__main__':
    n = 3
    print(Solution().climbStairs(n))
# 思路：
# 爬楼梯问题，通常是指一个人从楼梯的顶端开始，每次可以选择向上走1步或2步，问走n步有多少种不同的走法。
# 这是一个动态规划问题，我们可以用数组dp[i]表示爬到第i级台阶的方法数。
# 对于第i级台阶，有两种方法：
# 1. 从第i-1级台阶爬上来，此时dp[i] = dp[i-1]
# 2. 从第i-2级台阶爬上来，此时dp[i] = dp[i-1] + dp[i-2]
# 因此，dp[i] = dp[i-1] + dp[i-2]
# 最后，dp[n]即为走n步的方法数。
# 时间复杂度：O(n)，空间复杂度：O(n)
